8. Self-consistency and the EM algorithm
The term self-consistency was, to our knowledge, first used by Efron (1967) to describe a class of estimators of a distribution function \(F(t)\) in the presence of censored data.
self-consistency는 Efrom이 처음 썼고, censored data가 있을때 distribution finction의 estimator로 설명되었다.
If \(x_1, \dots , x_N\) are observed data from a distribution \(F\), the nonparametric maximum likelihood estimate of \(F\) is \(\hat{F}(t) = \sum_{i=1}^N I[x_i \le t]/N\), where \(I[\dot]\) is the indicator function.
만약 x1-xn이 F 분포의 observed data라면, F의 비모수 최대 우도 추정량은 f hat이다.
Indicator Function: 조건에 맞으면 1을 반환, 아니면 0을 반환
For all censored observations the function \(I[x_i < t]\) cannot be evaluated.
모든 censored 관찰값에서 I는 evaluate될 수 없다.
If \(y\) denotes the observed data, including censoring times for the censored observations, and \(F*\) denotes a distribution function, then \(\cal{P}\) \((x_i \le t | y, F * ) = E(I[ x_i \le t ] | y, F * )\) may be used to estimate \(I[x_i \le t]\) for all censored observations.
만약 y를 중단된 관찰값(결측값)에 대한 중단된 시간을 포함한 관찰값이라고 놓고, F * 를 distribution function 으로 보면, p=E는 모든 censored 관찰값에 대한 추정치로 사용될 것이다.
A distribution function \(F *(t)\) is called a self-consistent estimate of the unknown distribution function \(F(t)\) if \(F * (t) = \frac{1}{N} \sum^N_{i=1} \cal{P}\) \((x_i \le t | y, F * )\) for all \(t\) (Efron, 1967; Laird, 1988).
distribution function F * 는 만약 F * 가 모든 t에 대해서 조건을 만족할때, 알려지지 않은 distribution function F의 self-consistent 추정값이라고 부른다.
That is, if we substitute the estimate \(F *\) in the calculation of the expected values, we obtain the same estimate \(F *\).
즉, 만약 기댓값으로 F * 의 추정값을 대체한다면, F * 의 같은 추정치를 얻을 수 있다.
In other words, the estimate \(F *\) “confirms itself.”
다시 말해서, 추정치 F * 는 F * 스스로 confirm한다(comfirms itself)
- 기댓값으로 자기 자신의 값을 구할 수 있다는 말인듯
In an iterative algorithm \(F *\) corresponds to a fixed point.
반복적인 알고리즘 F * 는 고정적인 점이다.
- 알려진 않은 값+ 알려지지 않은 값 = 이 분포를 추정하려 할때, 알려진 값을 고정 점으로 보고…기댓값 구할 수 있다는 말로 이해
This parallels the interpretation of self-consistent points in a k-means algorithm; see Section 9.
The expectation-maximization (EM) algorithm (Dempster, Laird and Rubin, 1967; Little and Rubin, 1987) is an iterative procedure for maximizing the log-likelihood in the presence of missing data.
EM 알고리즘은 결측값이 존재할때 로그 우도를 최대화하는 반복적인 과정이다.
Suppose we have a model for complete data \(X\), with density \(f(x, \theta)\) indexed by an unknown parameter \(\theta\).
complete data X에 대한 알려지지 않은 파라메터 theta에 의해 index된 density f가 있는 model을 가지고 있다고 가정해보자.
- 결측값 인덱스에는 값이 없고, 값이 있는 인덱스에는 값이 있는
Write \(X = (X_{obs}, X_{mis})\), where \(X_{obs}\) represents the observed part of the data, and \(X_{mis}\) the missing part.
xobs는 관찰된 부분의 데이터이고, xmis는 결측값 부분의 데이터이다. x는 xobs, xmis로 이뤄져 있다고 해보자.
Let \(l(\theta |X)\) denote the complete data log-likelihood, and let \(\theta^{(t)}\) denote the current value of the parameter estimate in iteration \(t\) of the EM algorithm.
l(theta)를 complete데이터의 로그우도로 보고, theta의 t제곱을 EM알고리즘의 반복을 의미하는 t의 모수 추정치의 현재값으로 정의하자.
- EMEMEM 그 반복의 t 번째
- t 번 업데이트하는 거랑 EM알고리즘의 EM반복이랑 동일하게
Each iteration of the EM algorithm consists of an E (expectation) step and an M (maximization) step.
EM 알고리즘의 각 반복은 기댓값 E 단계와 최댓값 M 단계로 이루어져 있다.
The E step corresponds to taking the expectation of the complete data log-likelihood, given the observed data \(X_{obs}\), and using the current value \(\theta^{(t)}\) of the parameter estimate.
E 단계는 xobs 값이 주어졌을때, 모수 추정치의 t번 반복하여 얻은 theta를 사용하여 complete 데이터 로그 우도값의 기댓값을 가진다.
That is, the E step computes \(Q(\theta, \theta^{(t)} ) = E[l(\theta ; X) |X_{obs} , \theta^{(t)} ]\).
즉, E 단계는 Q를 얻게 된다.
The M step then finds \(\theta^{(t+1)}\) which maximizes \(Q(\theta, \theta^{(t)})\) over all \(\theta\) in the parameter space.
M 단계는 모수 공간에서 모든 theta에 걸쳐 Q함수를 최대화하는 theta의 t+1번째 반복값을 구할 수 있다.
Convergence is reached if \(\theta^{(t+1)} = \theta^{(t)}\).
theta의 t+1번째 반복값이 theta의 t번째 반복값과 같게 된다면 수렴의 공간에 도달한다.
Thus the final estimate, denoted by \(\hat{\theta}\), is again a fixed point of the algorithm, and the estimate \(\hat{\theta}\) “confirms itself” in any further iteration of the algorithm.
그러므로 theta_hat의 마지막 추정치(마지막 반복값)는 다시 알고리즘의 fixed point가 된다. 그리고 그 추정치 theta_hat은 어느 반복 알고리즘에서 confirms itself 한다.
The EM algorithm has been shown to converge under general conditions to a maximum of the likelihood function based on the observed data \(X_{obs}\).
이 EM 알고리즘은 관찰값 xobs를 기반으로 우도 함수의 최대화를 위한 일반적인 조건 아래 수렴하는 것으로 보여져 왔다.
Since an iteration of the EM algorithm can never decrease the log-likelihood, Cox and Oakes (1984, page 171) define the self-consistency condition for the maximum likelihood estimator \(\hat{\theta}\) as \(Q(\theta , \hat{\theta} ) \le Q ( \hat{\theta} , \hat{\theta})\) for all \(\theta\) in the parameter space.
EM알고리즘의 iteration은 절대 로그우도를 감소시킬 수 없기 때문에 cox,oakes는 모수 공간에서 모든 theta에 대하여 위 식에 따라 최대 우도 추정치 theta_hat에 대한 self-consistency 조건을 정의했다.
- Em 알고리즘이 로그 우도를 최대화 하여 최적의 expectation값을 구한다는 조건을 이용해서 모수를 넣은 Q값보다 추정치를 넣은 Q가 크거나 작다면 self-consistency를 만족한다고 정의한듯!
If the density of the complete data X is from the exponential family, we can establish a direct connection between our notion of self-consistency and the notion of a self-consistent estimator just explained.
만약 complete data x의 밀도가 exponential family지수족에서 온다면, self-consistency의 정의와 self-consistent 추정치의 정의 간 직접적인 연결성이 설명 될 수 있다고 할 수 있다.
Suppose \(X\) has a density of the form \(f(X; \theta) =b(X) exp [ \theta ' s(X)] /a(\theta)\), where \(\theta \in \mathbb{R}^d\) is a parameter vector, \(s(X)\) is a d-vector of complete-data sufficient statistics, and a and b are functions of \(\theta\) and \(X\), respectively.
theta가 d차원의 실수에 속하는 파라메터 벡터이고, s(x)는 complete 데이터 충분 통계량의 d-벡터이고, a,b 함수는 각각 theta, X의 함수인 함수 f의 density를 X가 가지고 있다고 가정해보자.
Then the E step simplifies to \(s^{(t)} = E[s(X) | X_{obs} , \theta^{(t)}]\).
그러면 E 단계가 단순화 된다.
By Lemma 2.5, \(s^{(t)}\) is self-consistent for \(s(X)\), that is, \(\cal{E}\) \([s(X)| s^{(t)}] = s^{(t)}\).
lemma 2.5에 의하면, s(t)는 s(X)에 대해 self-consistent하다.
LEMMA 2.5. Let \(X\) and \(Y\) denote two jointly distributed random vectors, not necessarily of the same dimension. Then \(\cal{E}\) \([X|Y]\) is self-consistent for \(X\).
The M step determines the updated estimate \(\theta^{(t+1)}\) as the solution of the equation \(E[s(X); \theta] = s^{(t)}\), based on which the next conditional expectation is taken.
M 단계는 다음 조건부 기댓값을 적용하기 위한 equation의 solution으로 업데이트된 theta 값을 결정한다.
Convergence is reached when the sequence \(\{ s^{(t)} \}_{t \ge 1}\) of self-consistent random variables has stabilized, that is, \(s^{(t+l)} = s^{(t)}\).
self-consistent 확률 변수 순열 s(t)이 업데이트 해도 변화가 거의 없는 안정화stablize 상태가 되었을때, 즉 s(t+1) = s(t)가 되었을때 수렴했다고 말한다.
Thus the EM algorithm generates a sequence of self-consistent random variables for a sufficient statistic \(s(X)\), and the maximum likelihood estimator, which corresponds to a stationary point in the sequence, satisfies the self-consistency condition as defined in Cox and Oakes(1984).
그러면 EM 알고리즘은 충분 통계량 s(x)에 대한 self-consistent 확률 변수의 순열로 일반화되고, 순열에서 stationary point와 상응하는 최대 우도 추정치는 self-consistency 조건을 만족한다.